import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @作者 钟先崟
 * @时间 2023-03-15 12:35
 * @说明
 */
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    public static void main(String[] args) {
        //[[2,4],[1,3],[2,4],[1,3]]
        Node a1 = new Node(1);
        Node a2 = new Node(2);
        Node a3 = new Node(3);
        Node a4 = new Node(4);
        a1.neighbors.add(a2);
        a1.neighbors.add(a4);
        a2.neighbors.add(a1);
        a2.neighbors.add(a3);
        a3.neighbors.add(a2);
        a3.neighbors.add(a4);
        a4.neighbors.add(a1);
        a4.neighbors.add(a3);
        Node node = cloneGraph(a1);
        node.neighbors.forEach((Node n) -> {
            System.out.print(n.val + " ");
        });
        node.neighbors.get(0).neighbors.forEach((Node n) -> {
            System.out.print(n.val + " ");
        });
        node.neighbors.get(1).neighbors.forEach((Node n) -> {
            System.out.print(n.val + " ");
        });
    }

    public static Node cloneGraph(Node node) {
        Node newNodes = null;
        if (node == null) return newNodes;
        newNodes = new Node(node.val);
        if (node.neighbors.size() == 0) return newNodes;
        Map<Integer, Node> record = new HashMap<>();
        searchGraph(node, newNodes, record);
        return newNodes;
    }

    public static void searchGraph(Node node, Node newNodes, Map<Integer, Node> map) {
        if (!map.containsKey(node.val)) {
            map.put(node.val, newNodes);
        }
        for (Node n : node.neighbors) {
            if (map.containsKey(n.val)) {
                newNodes.neighbors.add(map.get(n.val));
            } else {
                Node newNode = new Node(n.val);
                newNodes.neighbors.add(newNode);
                map.put(n.val, newNode);
                searchGraph(n, newNode, map);
            }
        }
    } //[[2,4],[1,3],[2,4],[1,3]]
}
